1. Field of the Invention
The present invention relates to an image processing method, apparatus and program for region segmentation of image data.
2. Description of the Related Art
The conversion of documents to electronic form goes beyond the mere acquisition of image data by reading a paper document using a scanner or the like. For example, image data is converted to an electronic form, it is separated into regions of different properties, such as the text, figures, photographs and tables that constitute a document. The process of converting the document to electronic form is used to execute processing that converts each region into data having the most suitable format. For example, a text region is converted to character code, a graphic region is converted to vector data, a background region or photographic region is converted to bitmap data, and a table region is converted to structure data.
For example, a conversion method using an image processing apparatus is disclosed in Japanese Patent Laid-Open No. 2007-158725 as a method of conversion to vector data. This image processing apparatus performs region segmentation by clustering processing, extracts the contour of each region and converts the extracted contour to vector data. Further, Japanese Patent Laid-Open No. 2008-206073 discloses an image processing method for separating an image into background and foreground, converts the foreground to vector data and subjects the background to data compression by a method exclusively for background. Further, Japanese Patent Laid-Open No. 2006-344069 discloses an image processing method for eliminating noise in a case where clustering processing has been applied to a document read by a scanner.
A method such as the nearest neighbor clustering method is known as a method for region segmentation of image data by clustering processing. The nearest neighbor clustering method compares the distances between the feature vector of a pixel of interest and the representative feature vectors of clusters and finds the cluster having the feature vector for which the distance is shortest. If the shortest distance found is less than a prescribed threshold value, then the pixel of interest is made to belong to the cluster. Otherwise, a new cluster is defined and the pixel of interest is made to belong to this cluster. In general, color information (a pixel value comprising R, G, B, for example) is used as the feature vector. The centroid of a cluster generally is used as the representative feature vector of the cluster. That is, the representative feature vector of a cluster is the average value of feature vectors (color information) of each of the pixels made to belong to the cluster.
With the nearest neighbor clustering method, the distances to the representative feature vectors of all clusters must be calculated pixel by pixel owing to the procedure described above. Accordingly, Japanese Patent Laid-Open No. 11-288465, for example, discloses a color image processing apparatus with the aim of reducing the amount of calculation. The apparatus of Japanese Patent Laid-Open No. 11-288465 performs clustering based upon a pixel of interest and the feature vector (color information) of a neighboring pixel, then performs grouping of clusters based upon the color information and geometrical information of clusters. The geometrical information is information such as coordinate information representing the closeness of regions.
The technology described in Japanese Patent Laid-Open No. 11-288465 is such that if the distance between the pixel of interest and the feature vector of the neighboring pixel is great, a cluster is defined anew and the pixel of interest is made to belong to this new cluster. A large quantity of clusters, therefore, are defined. A problem which arises as a consequence is a large increase in processing time needed to group the clusters.
A further problem is that performance for achieving the required processing time of the system cannot be assured owing to the increase in grouping processing time. The required processing time of the system refers to a critical processing time for assuring a constant performance such as scanner processing performance, namely the time it takes for the scanner to process one picture.